package dp01;



public class Solution2 {

    /**
     * 题目：不同路劲
     * 题目链接：https://leetcode.cn/problems/unique-paths/
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {           //行
            for (int j = 1; j <= n; j++) {       //列
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }


    /**
     * 题目：不同路劲||
     * 题目链接：https://leetcode.cn/problems/unique-paths-ii/
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(obstacleGrid[i-1][j-1] == 0) {       //没有障碍物（即该位置可以到达）
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
